using System;
using System.Collections.Generic;

// 二叉搜索树测试类
public class BinarySearchTreeTest
{
    public static void RunTest()
    {
        //测试用int key string value
        MyBST<int, string> bst = new();

        // 插入（相同键会覆盖旧值）
        bst.Put(5, "five");
        bst.Put(2, "two");
        bst.Put(8, "eight");
        bst.Put(1, "one");
        bst.Put(3, "three");

        // 查询
        Console.WriteLine("Get(3): " + bst.Get(3));         // three
        Console.WriteLine("ContainsKey(4): " + bst.ContainsKey(4)); // False

        // 有序操作
        Console.WriteLine("FirstKey: " + bst.FirstKey());   // 1
        Console.WriteLine("LastKey: " + bst.LastKey());     // 8
        Console.WriteLine("FloorKey(4): " + bst.FloorKey(4));   // 3
        Console.WriteLine("CeilingKey(4): " + bst.CeilingKey(4)); // 5

        // 秩/选择（0-based）
        Console.WriteLine("Rank(5): " + bst.Rank(5));       // 小于5的键数量=3（1,2,3）
        Console.WriteLine("SelectKey(2): " + bst.SelectKey(2)); // 第3小的键=3

        // 区间与所有键
        List<int> allKeys = bst.Keys();
        Console.WriteLine("Keys: " + string.Join(",", allKeys)); // 1,2,3,5,8
        List<int> range = bst.RangeKeys(2, 5);
        Console.WriteLine("Range[2,5]: " + string.Join(",", range)); // 2,3,5

        // 删除并再次查看
        bst.Remove(2);
        Console.WriteLine("After Remove(2) Keys: " + string.Join(",", bst.Keys()));
    }
}
public class TreeNode<K, V>
{
    public K key;
    public V value;
    public TreeNode<K, V> left;
    public TreeNode<K, V> right;
    public int size; //当前节点的子节点数量(包括自己)

    public TreeNode(K key, V value)
    {
        this.key = key;
        this.value = value;
        this.size = 1;
        this.left = this.right = null;
    }
}

// 基于二叉搜索树（BST）的有序映射
public class MyBST<K, V> where K : System.IComparable<K>
{
    private TreeNode<K, V> root;

    // ****** 工具方法 ******
    private int Size(TreeNode<K, V> node)
    {
        return node == null ? 0 : node.size;
    }

    public int Size()
    {
        return Size(root);
    }

    private TreeNode<K, V> RotateSize(TreeNode<K, V> node)
    {
        if (node != null) 
        {
            node.size = 1 + Size(node.left) + Size(node.right);
        }
        return node;
    }

    // ****** Map 键值映射的基本方法 ******
    // 增/改，复杂度 O(logN)。返回旧值（若不存在则返回 default(V)）
    public V Put(K key, V value)
    {
        V old = Get(key);
        root = Put(root, key, value);
        return old;
    }

    /// <summary>
    /// 插入节点
    /// </summary>
    /// <param name="node"></param>
    /// <param name="key"></param>
    /// <param name="value"></param>
    /// <returns></returns>
    private TreeNode<K, V> Put(TreeNode<K, V> node, K key, V value)
    {
        if (node == null) return new TreeNode<K, V>(key, value);
        //比较key和node.key 判断将新Node插入到node左还是右
        int cmp = key.CompareTo(node.key);
        if (cmp < 0)
        {
            node.left = Put(node.left, key, value);
        }
        else if (cmp > 0)
        {
            node.right = Put(node.right, key, value);
        }
        else
        {
            node.value = value;
        }
        return RotateSize(node);
    }

    /// <summary>
    /// 查，复杂度 O(logN) 作用为更新节点的Value
    /// </summary>
    /// <param name="key"></param>
    /// <returns></returns>
    public V Get(K key)
    {
        TreeNode<K, V> cur = root;
        while (cur != null)
        {
            int cmp = key.CompareTo(cur.key);
            if (cmp < 0) cur = cur.left;
            else if (cmp > 0) cur = cur.right;
            else return cur.value;
        }
        return default(V);
    }

    // 是否包含键 key，复杂度 O(logN)
    public bool ContainsKey(K key)
    {
        TreeNode<K, V> cur = root;
        while (cur != null)
        {
            int cmp = key.CompareTo(cur.key);
            if (cmp < 0) cur = cur.left;
            else if (cmp > 0) cur = cur.right;
            else return true;
        }
        return false;
    }

    // 删，复杂度 O(logN)
    public void Remove(K key)
    {
        root = Remove(root, key);
    }

    private TreeNode<K, V> Remove(TreeNode<K, V> node, K key)
    {
        if (node == null) return null;
        int cmp = key.CompareTo(node.key);
        if (cmp < 0)
        {
            node.left = Remove(node.left, key);
        }
        else if (cmp > 0)
        {
            node.right = Remove(node.right, key);
        }
        else
        {
            // 命中：Hibbard 删除
            if (node.right == null) return node.left;
            if (node.left == null) return node.right;

            TreeNode<K, V> t = node;
            node = Min(t.right);            // 用后继替换
            node.right = DeleteMin(t.right);
            node.left = t.left;
        }
        return RotateSize(node);
    }

    private TreeNode<K, V> Min(TreeNode<K, V> node)
    {
        if (node == null) return null;
        while (node.left != null) node = node.left;
        return node;
    }

    private TreeNode<K, V> Max(TreeNode<K, V> node)
    {
        if (node == null) return null;
        while (node.right != null) node = node.right;
        return node;
    }

    private TreeNode<K, V> DeleteMin(TreeNode<K, V> node)
    {
        if (node == null) return null;
        if (node.left == null) return node.right;
        node.left = DeleteMin(node.left);
        return RotateSize(node);
    }

    private TreeNode<K, V> DeleteMax(TreeNode<K, V> node)
    {
        if (node == null) return null;
        if (node.right == null) return node.left;
        node.right = DeleteMax(node.right);
        return RotateSize(node);
    }

    // 返回所有键的集合，结果有序（中序遍历），复杂度 O(N)
    public List<K> Keys()
    {
        List<K> res = new List<K>();
        Inorder(root, res);
        return res;
    }

    private void Inorder(TreeNode<K, V> node, List<K> acc)
    {
        if (node == null) return;
        Inorder(node.left, acc);
        acc.Add(node.key);
        Inorder(node.right, acc);
    }

    // ****** 有序操作 ******
    public K FirstKey()
    {
        TreeNode<K, V> m = Min(root);
        return m == null ? default(K) : m.key;
    }

    public K LastKey()
    {
        TreeNode<K, V> m = Max(root);
        return m == null ? default(K) : m.key;
    }

    // 小于等于 key 的最大键
    public K FloorKey(K key)
    {
        TreeNode<K, V> node = Floor(root, key);
        return node == null ? default(K) : node.key;
    }

    private TreeNode<K, V> Floor(TreeNode<K, V> node, K key)
    {
        if (node == null) return null;
        int cmp = key.CompareTo(node.key);
        if (cmp == 0) return node;
        if (cmp < 0) return Floor(node.left, key);
        TreeNode<K, V> t = Floor(node.right, key);
        return t != null ? t : node;
    }

    // 大于等于 key 的最小键
    public K CeilingKey(K key)
    {
        TreeNode<K, V> node = Ceiling(root, key);
        return node == null ? default(K) : node.key;
    }

    private TreeNode<K, V> Ceiling(TreeNode<K, V> node, K key)
    {
        if (node == null) return null;
        int cmp = key.CompareTo(node.key);
        if (cmp == 0) return node;
        if (cmp > 0) return Ceiling(node.right, key);
        TreeNode<K, V> t = Ceiling(node.left, key);
        return t != null ? t : node;
    }

    // 选择排名为 k 的键（0-based）。
    public K SelectKey(int k)
    {
        if (k < 0 || k >= Size()) return default(K);
        TreeNode<K, V> node = Select(root, k);
        return node == null ? default(K) : node.key;
    }

    private TreeNode<K, V> Select(TreeNode<K, V> node, int k)
    {
        if (node == null) return null;
        int leftSize = Size(node.left);
        if (k < leftSize) return Select(node.left, k);
        if (k > leftSize) return Select(node.right, k - leftSize - 1);
        return node;
    }

    // 键 key 的排名（严格小于 key 的键数量）
    public int Rank(K key)
    {
        return Rank(root, key);
    }

    private int Rank(TreeNode<K, V> node, K key)
    {
        if (node == null) return 0;
        int cmp = key.CompareTo(node.key);
        if (cmp < 0) return Rank(node.left, key);
        if (cmp > 0) return 1 + Size(node.left) + Rank(node.right, key);
        return Size(node.left);
    }

    // 区间查找 [low, high]，复杂度 O(logN + M)
    public List<K> RangeKeys(K low, K high)
    {
        List<K> res = new List<K>();
        RangeInorder(root, low, high, res);
        return res;
    }

    private void RangeInorder(TreeNode<K, V> node, K low, K high, List<K> acc)
    {
        if (node == null) return;
        if (low.CompareTo(node.key) < 0) RangeInorder(node.left, low, high, acc);
        if (low.CompareTo(node.key) <= 0 && high.CompareTo(node.key) >= 0) acc.Add(node.key);
        if (high.CompareTo(node.key) > 0) RangeInorder(node.right, low, high, acc);
    }
}
